package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/1
 * @Description: 堆排序
 * @version: 1.0
 */
public class HeapSort {
    //元素下沉
    private static void down(int[] arr, int parent, int size) {
        while (true) {
            int left = parent * 2 + 1;
            int right = parent + 1;
            int max = parent;
            if (left < size && arr[left] > arr[max]) {
                max = left;
            }
            if (right < size && arr[right] > arr[max]) {
                max = right;
            }
            if (max != parent) {
                swap(arr, parent, max);
                parent = max;
            }
        }

    }

    //交换元素
    private static void swap(int[] arr, int parent, int max) {
        int tem = arr[parent];
        arr[parent] = arr[max];
        arr[max] = tem;
    }

    //建立大顶堆
    private static void getHeap(int[] arr, int size) {
        for (int i = size / 2 - 1; i > 0; i--) {
            down(arr, i, size);
        }
    }

    //堆排序
    /*
     *  时间复杂度: 最好O(nlogn)  最坏O(nlogn)  平均最坏O(nlogn)
     *  空间复杂度: O(1)
     */
    public static int[] sort(int[] arr) {
        getHeap(arr, arr.length);
        for (int right = arr.length - 1; right > 0; right--) {
            swap(arr, 0, right);
            down(arr, 0, right);
        }
        return arr;
    }

}
